package com.chilly.linkedlist;

/**
 * 160. 相交链表
 * <p>
 * Created by Chilly Cui on 2020/11/30.
 */
public class IntersectionOfTwoLinkedLists {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;

        ListNode listNode11 = new ListNode(11);
        ListNode listNode22 = new ListNode(3);
        ListNode listNode33 = new ListNode(4);
        listNode11.next = listNode22;
        listNode22.next = listNode33;

//        ListNode node = new Solution().getIntersectionNode(listNode, listNode11);
        ListNode node = new Solution().getIntersectionNode(null, null);
        System.out.println(node);

    }

    static class Solution {

        /**
         * 两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}
         *
         * 双指针法：
         * 1、创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历
         * 2、当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点
         * 3、当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点
         * 4、若在某一时刻 pA 和 pB 相遇，则 pA/pB 为相交结点。
         *
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode pa = headA;
            ListNode pb = headB;

            while (pa != pb) {
                pa = pa == null ? headB : pa.next;
                pb = pb == null ? headA : pb.next;
            }
            return pa;
        }

        /*public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int skipA=0;
        int skipB=0;
        while(headA != null && headB!=null){
            if(headA.val != headB.val){
                skipA++;
                skipB++;
            }else{
                return new ListNode(headA.val);
            }
        }
        return null;
    }
    */

    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
}
